<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8" />
  <meta http-equiv="X-UA-Compatible" content="IE=edge" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <title>Document</title>
</head>

<body>
  <script>
    // const { connectStart, connectEnd } = window.performance.timing
    // console.log(connectStart - connectEnd)
    // console.log(window.performance)

    // 1. 冒泡排序: 元素一和元素二比较，元素二大于元素一，交换位置；元素二和元素三比....
    // 优化   1. 可能传入的数据已经是有序列表
    //        2. 可能列表后面的已经是排序的（记录一次循环中最后一次交换的位置）
    function bubbleSort(array) {
      var cnt = 0
      for (let end = array.length - 1; end > 0; end--) {
        // sortIndex的初始值在数组完全有序的时候有用，end初始值要适合外层for循环条件
        // 如果大于等于2并且数据完全有序将会死循环
        let sortIndex = 1
        for (let begin = 1; begin <= end; begin++) {
          cnt++
          if (array[begin] < array[begin - 1]) {
            [array[begin], array[begin - 1]] = [array[begin - 1], array[begin]]
            sortIndex = begin
          }
        }
        end = sortIndex
      }
      console.log(cnt)
      return array
    }
    // console.log(bubbleSort([2, 1, 8, 3, 7, 6, 4, 9, 10, 11, 12, 13, 1]))

    // 2. 选择排序：遍历自身以后的元素，最小的元素跟自己换位置
    function selectSort(arr) {
      let len = arr.length
      for (let i = 0; i < len; i++) {
        for (let j = i; j < len; j++) {
          if (arr[j] < arr[i]) {
            ;[arr[i], arr[j]] = [arr[j], arr[i]]
          }
          // console.log(arr[i], arr[j], i, j)
        }
      }
      return arr
    }

    // 3. 插入排序：将元素插入已排序好的数组中(对未排序序列中从后向前扫描，找到对应位置并插入)
    function insertSort(arr) {
      for (let i = 1; i < arr.length; i++) {
        // arr[0]默认为已排序的数组
        for (let j = i; j > 0; j--) {
          if (arr[j] < arr[j - 1]) {
            ;[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
          } else {
            break
          }
          // console.log(arr[j], arr[j - 1], j, j - 1, i)
          // console.log(arr)
        }
      }
    }
    // [5, 6, 3, 4, 1, 2]
    // 5, 6, 3, 4, 1, 2 -> 5,3,6,4,1,2 -> 3,5,6,4,1,2
    // 3,5,4,6,1,2 -> 3,4,5,6,1,2

    // console.log(insertSort([5, 6, 1, 7, 3, 2, 8, 4]))

    // 4. 希尔排序
    function shellSort(arr) {
      let len = arr.length
      for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        console.log('gap', gap)
        for (let i = gap; i < len; i++) {
          let j = i // 3
          let current = arr[i] // 7
          console.log(j, gap, current, arr[j - gap])
          //  4  3     3       6
          //  3  3     7       5
          while (j - gap >= 0 && current < arr[j - gap]) {
            arr[j] = arr[j - gap]
            j = j - gap
          }

          arr[j] = current
          console.log(arr)
        }
      }
      return arr
    }

    // 5. 归并排序
    //    归并排序采用的是分治的思想，首先是‘分’，将一个数列反复二分为两个小数组，直到每个数组只有一个元素
    //    其次是‘治’，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小
    //    创建临时数组
    //    从两个数组的开始元素开始比较，A[0] B[0]比较，小的放到临时数组，A[1] B[0]比较...
    //    将另一序列剩下的所有元素直接复制到合并序列尾
    //    [6,1,8,2, 3] ... =>[6][1][8][2][3] => [1,6][2,8,3] => [1,2,3,6,8]
    function mergeSort(array) {
      let len = array.length
      if (len <= 1) return array

      let num = Math.floor(len / 2)
      let left = mergeSort(array.slice(0, num))
      let right = mergeSort(array.slice(num, len))

      return merge(left, right)

      function merge(left, right) {
        let [l, r] = [0, 0]
        let result = []
        while (l < left.length && r < right.length) {
          if (left[l] <= right[r]) {
            result.push(left[l])
            l++
          } else {
            result.push(right[r])
            r++
          }
        }
        result = result.concat(left.slice(l, left.length))
        result = result.concat(right.slice(r, right.length))
        return result
      }
    }

    // 6. 快速排序：选择基准mid，循环原数组，小于基准值放左边数组，大于放右边数组，
    //    然后concat组合，最后依靠递归完成排序 (把数组递归切割为一个元素的数组，然后concat组合)
    function quickSort(arr) {
      if (arr.length <= 1) return arr
      // 定义两个数组增加空间复杂度
      let left = []
      let right = []

      const pivotIndex = Math.floor(arr.length / 2)
      // 调用splice更耗时
      let mid = arr.splice(pivotIndex, 1)
      for (let i = 0; i < arr.length; i++) {
        if (arr[i] < mid) {
          left.push(arr[i])
        } else {
          right.push(arr[i])
        }
      }
      // console.log(left, mid, right)
      return quickSort(left).concat(mid, quickSort(right))
    }

    // 7. 堆排序
    // 堆排序
    function heapSort(arr) {
      // 初始化大顶堆，从第一个非叶子结点开始
      for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
        shiftDown(arr, i, arr.length)
      }

      // 排序，每一次for循环找出一个当前最大值，数组长度减一
      for (let i = Math.floor(arr.length - 1); i > 0; i--) {
        swap(arr, 0, i) // 根节点与最后一个节点交换
        shiftDown(arr, 0, i) // 从根节点开始调整，并且最后一个结点已经为当
        // 前最大值，不需要再参与比较，所以第三个参数
        // 为 i，即比较到最后一个结点前一个即可
      }
      return arr
    }

    // 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
    // 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
    // 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
    // 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
    // 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
    //顶堆
    function shiftDown(arr, i, length) { // [5, 6, 1, 7, 3, 2, 8, 4]
      let temp = arr[i] // 当前父节点
      // j<length 的目的是对结点 i 以下的结点全部做顺序调整
      for (let j = 2 * i + 1; j < length; j = 2 * j + 1) {
        temp = arr[i] // 将 arr[i] 取出，整个过程相当于找到 arr[i] 应处于的位置
        if (j + 1 < length && arr[j] < arr[j + 1]) {
          j++ // 找到两个孩子中较大的一个，再与父节点比较
        }
        if (temp < arr[j]) {
          swap(arr, i, j) // 如果父节点小于子节点:交换；否则跳出
          i = j // 交换后，temp 的下标变为 j
        } else {
          break
        }
      }
    }

    // 交换两个节点
    function swap(A, i, j) {
      let temp = A[i]
      A[i] = A[j]
      A[j] = temp
    }
    
    console.log(heapSort([5, 6, 1, 7, 3, 2, 8, 4]))
      // console.log(window.performance)



  </script>
</body>

</html>